The present invention relates to arithmetic integrated circuits. In particular, the invention relates to apparatus for arithmetic division operations.
Many sophisticated microelectronic devices employ microprocessing devices. Microprocessors, whether for general purpose computers, or for specially configured signal processors and similar special-purpose devices, employ some form of arithmetic unit for calculating arithmetic operations. One of the most common arithmetic operations is the division of one number by another. The arithmetic operation of division, whether for integer or floating point operations, computes successive quotient digits. Unlike other arithmetic operations (such as addition or multiplication), in division the resulting quotient digits are always calculated from the most-signficant digit to the least significant. That is, dividing 100 by 5, one first finds that the quotient has a 2 in the 10's digit and, then finds a zero in the 1's digit (and zeroes in every successive digit).
Conventional arithmetic units usually generate each quotient digit sequentially, storing these digits temporarily until all of the digits are available as a final answer. Arithmetic units usually store these digits in a shift register designed to shift previous digits as each new digit is formed. The shift register can deliver a final quotient answer only when all of the digits have been generated to the required precision.
Division, especially for high-precision applications, can be enormously time-consuming. However, it is well known that sequences of quotient digits will repeat when the dividend and the divisor form a rational fraction. This feature of division makes some form of time savings feasible, in theory, by detecting this repetition early and halting the calculation process. Yet current arithmetic hardware does not implement such early detection. The complete series of calculations are always performed because it would take just as much area and time delays to add additional logic to replicate a repeating series of digits and to steer the digits to their correctly aligned positions. Because no perceived time-savings has been demonstrated, designers of conventional arithmetic units have not bothered to incorporate any apparatus to detect repeating quotient digit series. Therefore, most division apparatus has a constant time delay independent of operands. For example, to compute a 53-bit answer to 1/2 normally takes just as long as to compute the 53-bit answer to 1/7.
Current microelectronic technology methods and apparatus do not provide a simple, time-saving means for detecting patterns of repeating quotient digits, and for terminating division processes early. What is needed is an improved method and apparatus for detecting quotient repetition, and for completing quotients early. The improved apparatus and method should provide a simply implemented system for discovering quotient repetitions without adding inordinate hardware and delay overhead. The apparatus and method should be sufficiently flexible to implement the early repetition detection and quotient completion with a variety of hardware platforms, logic architectures and system requirements.